package algorithm.sort;

import java.util.Random;

public class practiceSort {
	public static void main(String[] args){
		int[] arrylist = {10,5,88,65,22,35,3,61,41,86,99,52};
		int[] arrylist2 = {10,5,88,65,22,35,3,61,41,86,99,52};
		
		practiceSort ps = new practiceSort();
		
		System.out.print("排序前数组为： ");
		ps.printFunc(arrylist);
		
		ps.quickSort_asc(arrylist, 0, arrylist.length-1);
		System.out.print("快速升序排序后数组为：");
		ps.printFunc(arrylist);
		
		int[] list1 = ps.bubbleSort_asc(arrylist);
		System.out.print("冒泡升序排序后数组为：");
		ps.printFunc(list1);
		
		
		int[] list2 = ps.bubbleSort_desc(arrylist2);
		System.out.print("冒泡降序排序后数组为：");
		ps.printFunc(list2);
		
		System.out.print("原数组为：");
		ps.printFunc(arrylist);
		
		
		System.out.print("冒泡升序排序后数组为：");
		ps.printFunc(list1);

		
		System.out.println("升序列表中查找数值为52的下标为： "+ps.searchItem(arrylist, 52, "asc"));

		System.out.println("降序列表中查找数值为44的下标为： "+ps.searchItem(list2,44, "desc"));
	}
	
	//冒泡排序:从小到大排序
	public int[] bubbleSort_asc(int[] list){
		int temp;
		int[] arry = list;
		for(int i=0;i<list.length;i++){
			for(int j=i+1;j<list.length;j++){
				if(list[j] < list[i]){
					temp = list[i];
					list[i] = list[j];
					list[j] = temp;
				}
			}
		}
		return arry;
	}
	
	//冒泡排序：从大到小排序
	public int[] bubbleSort_desc(int[] list){
		int temp;
		int[] arry = list;
		for(int i=0;i<list.length;i++){
			for(int j=i+1;j<list.length;j++){
				if(list[i] < list[j]){
					temp = list[i];
					list[i] = list[j];
					list[j] = temp;
				}
			}
		}
		return arry;
	}
	
	//快速排序：从小到大排序
	public void quickSort_asc(int[] list,int left,int right){
		int i = left;
		int j = right;
		int base = list[left];  //将数组中左边的第一个元素作为基数
		
		if(left >= right){
			return;
		}
		
		while(i != j){
			while(i<j && base<=list[j])
				j--;
			
			if(i < j)
				list[i] = list[j];
			
			while(i<j && list[i]<base)
				i++;
			
			if(i < j)
				list[j] = list[i];
		}
		
		list[i] = base;
		
		if(i > left)
			quickSort_asc(list,left,i-1);
		
		if(j < right)
			quickSort_asc(list,i+1,right);
	}
	
	//二分查找
	public int searchItem(int[] list,int item,String mode){
		int starnum = 0;
		int endnum = list.length-1;
		int midnum = (starnum+endnum)/2;
		
		//升序模式下查找
		while(starnum<=endnum && mode.equals("asc")){
			if(item < list[midnum])
				endnum = midnum - 1;
			
			if(item > list[midnum])
				starnum = midnum +1;
			
			if(item == list[midnum])
				return midnum;
			
			midnum = (starnum + endnum)/2;
		}

		//降序模式下查找
		while(starnum<=endnum && mode.equals("desc")){
			if(item > list[midnum])
				endnum = midnum - 1;
			
			if(item < list[midnum])
				starnum = midnum +1;
			
			if(item == list[midnum])
				return midnum;
			
			midnum = (starnum + endnum)/2;
		}
		
		return -1;
	}
	
	//输出
	public  void printFunc(int[] list){
		for(int i=0;i<list.length;i++){
			System.out.print(list[i] + "  ");
		}
		System.out.println();
	}
}
